R.: A theory of “may” testing for asynchronous languages

Abstract. Asynchronous communication mechanisms are usually at the basis of real distributed systems and protocols. For these systems, asyn-chronous may-based testing seems to be exactly what is needed to cap-ture safety and certain security properties. We study may testing equivalence focusing on the asynchronous versions of CCS and pi-calculus. We start from an operational testing preorder and provide finitary and fully abstract trace-based models for it, together with complete inequational axiomatizations. The results throw light on the differences between synchronous and asynchronous systems and on the weaker testing power of asynchronous observations.